package QuestionDaily;

import java.util.HashMap;

public class firstCompleteIndex_2661 {
    /**
     * 从下标 0 开始遍历 arr 中的每个下标 i ，并将等于 arr[i] 的 mat 对应单元格涂色。
     * arr 和 mat 都包含范围 [1，m * n] 内的 所有 整数
     * 当mat 的某一行或某一列上全都被涂色时
     * 返回其下标 i 。
     */
    public int firstCompleteIndex(int[] arr, int[][] mat) {
        /**
         * 因为数字各不相同，使用hashmap映射每一个数字对应位置
         * 25ms, hashmap内部检索数据比我想象的慢
         */
        int m=mat.length,n=mat[0].length;
        int[]row=new int[m]; //记录每一行被填了几个格子
        int[]col=new int[n];
        //创建位置映射
        HashMap<Integer,int[]>reflect=new HashMap<>();
        for(int i=0;i<m;i++){
            for(int t=0;t<n;t++){
                int[] position={i,t};
                reflect.put(mat[i][t],position);
            }
        }
        for(int i=0;i<arr.length;i++){
            int[] position=reflect.get(arr[i]); //位置信息
            row[position[0]]++; //对应行列被填数量加1
            col[position[1]]++;
            if(row[position[0]]==n || col[position[1]]==m) //  当mat 的某一行或某一列上都被涂色时
                return i;
        }
        return 0;
    }

    /**
     * 高解3ms
     * 索引二维转一维 + 状态小压缩，避免使用hashmap
     * 思路 ：
     * ma[i][j] 二维压缩至一维，压缩后 ：index = i * n + j
     * fill记录每一行或每一列的填充情况, [0,m)[0,m)[0,m)表示行的填充，[m,m+n][m, m + n][m,m+n]表示列填充
     * @param arr
     * @param mat
     * @return
     */
    public int firstCompleteIndex2(int[] arr, int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[] fill = new int[m + n];
        int[] map = new int[m * n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                map[mat[i][j]] = i * n + j;
            }
        }

        for (int i = 0; i < m * n; i++) {
            int index = map[arr[i]], x = index / n, y = index % n;
            if (++fill[x] == n) return i;
            if (++fill[m + y] == m) return i;
        }
        return -1;
    }
}
